#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

struct Stack {
    int top;
    int data[MAX_SIZE];
};

void initStack(struct Stack* stack) {
    stack->top = -1;
}

int isEmpty(struct Stack* stack) {
    return stack->top == -1;
}

int isFull(struct Stack* stack) {
    return stack->top == MAX_SIZE - 1;
}

void push(struct Stack* stack, int item) {
    if (isFull(stack)) {
        printf("Error: Stack is full\n");
        return;
    }
    stack->data[++(stack->top)] = item;
}

int pop(struct Stack* stack) {
    if (isEmpty(stack)) {
        printf("Error: Stack is empty\n");
        return -1;
    }
    return stack->data[(stack->top)--];
}

void printQueens(int* queens, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (queens[i] == j) {
                printf("Q ");
            } else {
                printf(". ");
            }
        }
        printf("\n");
    }
    printf("\n");
}

int isSafe(int* queens, int row, int column) {
    for (int i = 0; i < row; i++) {
        if (queens[i] == column || abs(i - row) == abs(queens[i] - column)) {
            return 0;
        }
    }
    return 1;
}

void nQueens(int n) {
    struct Stack stack;
    initStack(&stack);

    int* queens = (int*)malloc(sizeof(int) * n); 

    int row = 0, column = 0;

    while (1) {
        while (row < n && column < n) {
            if (isSafe(queens, row, column)) {
                queens[row] = column; 
                push(&stack, row);    
                row++;
                column = 0;
            } else {
                column++;
            }
        }

        if (row == n) {
            printQueens(queens, n); 
        }

        if (isEmpty(&stack)) {
            break;
        }

        row = pop(&stack);         
        column = queens[row] + 1;  
        queens[row] = -1;          
    }

    free(queens);
}

int main() {
    int n = 4; 
    nQueens(n);

    return 0;
}